package net.tp.algo.text;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 
* @author Trung Phan
*
*/
public class SearchText {

    /**
     * Space of character set. Use 256 for demonstration purpose. For java unicode, R = Integer.MAX_VALUE.
     */
    public final static int R = 256;
    
    /**
     * 
     * <p>Brute-force with backup. To understand Knuth-Morris-Pratt, one would need to understand
     * brute-force with backup algorithm. Every time a mismatch is detected, we backup the iteration
     * i to do search again.</p>
     * 
     * <p>Running time: O(mn)</p>
     * 
     * @param text text to search
     * @param searchString pattern
     * @return match position, -1 if no match
     */
    public static int bruteforce(String text, String searchString) {
        
        int n = text.length();
        int m = searchString.length();
    
        int i = 0;
        int matches = 0;
        while (true) {
            if (matches == m) { // found m number of matches
                return i - matches;
            }
            if (i == n) {
                return -1;
            }
            
            char c = text.charAt(i);
            char expected = searchString.charAt(matches);
            if (c == expected) {
                matches++;
            }
            else if (matches > 0) {
                i -= matches; // backup
                matches = 0; // reset matches
            }
            
            i++;
        }
    }
    
    /**
     * 
     * <p>Knuth-Morris-Pratt algorithm using Deterministic finite state machine.
     * To understand Knuth-Morris-Pratt algorithm, one needs to understand the brute-force algorithm with backup.
     * The objective of algorithm is to avoid backup. To do that, it needs to pre-calculate the deterministic
     * finite state automation (DFA). Using this DFA, the algorithm can determine the next state once a match or
     * mismatch is encountered. Once the state reaches m (pattern's length), the pattern is found within the text.
     * The DFA table will look like this for pattern ABABAC:</p>
     * 
     * <pre>
     *    Pattern →  A   B   A   B   A   C
     *      State →  0   1   2   3   4   5
     *          A    1   1   3   1   5   1
     *          B    0   2   0   4   0   4
     *          C    0   0   0   0   0   6
     * </pre>
	 * 
	 * 
	 * @param text text to search
	 * @param pattern pattern
	 * @return match position, -1 if no match
	 * @throws NullPointerException if text or searchString is null
	 * @see SearchText#bruteforce(String, String)
	 */
	public static int searchTextByDFA(String text, String pattern) {
		
		int n = text.length();
		int m = pattern.length();
		
		if (m == 0) {
			return 0;
		}
		if (m > n) {
			return -1;
		}
		
		int[][] dfa = computeDFA(pattern);
		
		int state = 0;
		for (int i = 0; i < n; i++) {
			char c = text.charAt(i);
			state = dfa[c] != null ? dfa[c][state] : 0;
			
			if (state == m) {
				return i + 1 - m;
			}
		}
		
		return -1;
	}
	
	/**
	 * <p>How to compute Deterministic finite state automation (DFA).<p>
	 * 
	 * <p>Take this example of DFA for pattern ABABAC:<p>
     * <pre>
     *    Pattern →  A   B   A   B   A   C
     *      State →  0   1   2   3   4   5
     *          A    1   1   3   1   5   1
     *          B    0   2   0   4   0   4
     *          C    0   0   0   0   0   6
     * </pre>
	 * 
	 * <p>Assume that the table DFA have been built up to state 4 for all row A, B, C; how do
	 * we build the table for state 5. How do we know that state should go back to 1 if A is encountered and back to 4
	 * if B is encountered? Once the state reaches 5, we know that the current search is matching up to 5 characters
	 * ABABA and the expected next character is C. The text will look like this at this point: .....ABABA?.....
	 * When the mismatch is encountered at this state (i.e. C is not encountered), we pretend that we have to backup
	 * iterator i and do the search again from .....A<u>BABA?</u>.... . To find out where the state would be if
	 * character ? is encountered, we just have to run BABA? again through the DFA. In this case, if BABA is run through
	 * the DFA, the state would have been 3: 0 <sup>B</sup>&rarr; 0 <sup>A</sup>&rarr; 1 <sup>B</sup>&rarr; 2 <sup>A</sup>&rarr; 3.
	 * So if ? is A, the state would be 1 and if ? is B, the state would be 4.</p>
	 * 
	 * <p>It looks like the DFA pre-calculation is not efficient if we have to run the pattern segment [1..i-1] through the DFA
	 * for each state i. For example, to calculate state transition for state 5, we have to calculate what state X would
	 * be if we have to run the pattern BABA again through the DFA. We can in fact cache this state X once we
	 * finish calculation of DFA for each state i. Then we don't have to run the whole pattern [1..i-1] again through
	 * the DFA. For example, assume we are filling the DFA table for state 3, we need to know what state X would be if
	 * we would have run the pattern BA through the DFA. State X in this case equals to 1: 0 <sup>B</sup>&rarr; 0 <sup>A</sup>&rarr; 1.
	 * We cache the value 1 for X. Then assume we finish the state 3 and start filling the DFA table for state 4. To fill info for
	 * state 4, we need to know what state X would be if we run BAB through the DFA. But since we cache the state X = 1
	 * for pattern BA, the next state X for pattern BAB will be 2: 1 <sup>B</sup>&rarr; 2. So it takes O(mC + R) time and space to build the DFA
	 * where C is the number of distinct characters in the pattern and R is the space of the character set.
	 * </p>
	 * 
	 * <p>To build the DFA, first fill in the match which is easy:</p>
     * <pre>
     *    Pattern →  A   B   A   B   A   C
     *      State →  0   1   2   3   4   5
     *          A    1   -   3   -   5   -
     *          B    -   2   -   4   -   -
     *          C    -   -   -   -   -   6
     * </pre>
	 * 
	 * <p>Then fill in the first state: state 0</p>
	 * 
     * <pre>
     *    Pattern →  A   B   A   B   A   C
     *      State →  0   1   2   3   4   5
     *          A    1   -   3   -   5   - 
     *          B    0   2   -   4   -   - 
     *          C    0   -   -   -   -   6
     * </pre>
	 * 
	 * @param pattern pattern
	 * @return DFA matrix
	 */
	public static int[][] computeDFA(String pattern) {
		assert pattern != null && pattern.length() > 0 : "searchString must not be empty.";
		
		int[][] dfa = new int[R][];
		List<Character> chars = new ArrayList<>();
		
		int m = pattern.length();
		
		// happy path: match cases
		for (int i = 0; i < m; i ++) {
			char c = pattern.charAt(i);
			if (dfa[c] == null) {
				chars.add(c);
				dfa[c] = new int[m];
			}
			dfa[c][i] = i+1;
		}
		
		// mismatch cases:
		// state 0: nothing to do: every mismatch goes back to 0 (which is already initialized in the new int[]
		// column 1 onwards:
		for (int x = 0, state = 1; state < m; state++ ) {
			char expectedChar = pattern.charAt(state);
			for (char c : chars) {
				if (c != expectedChar) {
					dfa[c][state] = dfa[c][x];
				}
			}
			x = dfa[expectedChar][x];
		}
		
		return dfa;
	}
	
	/**
	 * <p>Knuth-Morris-Pratt algorithm using Failure function.</p>
	 * @param text text to search
	 * @param pattern pattern
	 * @return match position, -1 if no match
	 */
	public static int searchTextByFailureFunction(String text, String pattern) {
		
		int n = text.length();
		int m = pattern.length();
		
		int[] ff = computeFailureFunction(pattern);
		
		int i = 0;
		int matches = 0;
		while (true) {
			if (matches == m) {
				return i - m;
			}
			if (i == n) {
				return -1;
			}
			
			char c = text.charAt(i);
			char expected = pattern.charAt(matches);
			
			if (c == expected) {
				i++;
				matches++;
			}
			else if (matches == 0) {
				i++;
			}
			else {
				matches = ff[matches];
			}
		}
	}
	
	/**
	 * 
	 * Failure function f(j) is the length of the longest prefix of pattern P that is also a suffix of P[0..j].
	 * 
	 * 
	 * @param pattern pattern
	 * @return failure values
	 * @see <a href="http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/kuthMP.htm" target="_top">
	 * http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/kuthMP.htm</a>
	 */
	public static int[] computeFailureFunction(String pattern) {
		
		int m = pattern.length();
		int[] ff = new int[m];
		
		if (m == 0) {
			return ff;
		}
		
		ff[0] = 0;
		int matches = 0;
		int i = 1;
		while (i < m) {
			
			char c = pattern.charAt(i);
			char expected = pattern.charAt(matches);
			
			if (c == expected) {
				matches++;
				ff[i] = matches;
				i++;
			}
			else if (matches == 0) {
				ff[i] = 0;
				i++;
			}
			else {
				matches = ff[matches-1]; // ff[matches-1] is the longest prefix that is also the subfix of P[0..matches-1]
			}
		}
		
		return ff;
	}
	
	
	public static int searchTextByLastFunction(String text, String pattern) {
		
		int n = text.length();
		int m = pattern.length();
		if (m == 0) {
			return 0;
		}
		
		int[] lf = computeLastFunction(pattern);
		
		int skip = 0;
		for (int i = 0; i <= n - m; i += skip) {
			int j = m - 1;
			while (j >= 0) {
				char c = text.charAt(i + j);
				char expected = pattern.charAt(j);
				if (c == expected) {
					j--;
				}
				else {
					skip = Math.max(1, j-lf[c]);
					break;
				}
			}
			if (j == -1) return i;
		}
		
		return -1;
	}
	
	
	
	public static int[] computeLastFunction(String pattern) {
		
		int[] lf = new int[R];
		Arrays.fill(lf, -1);
		for (int i = 0; i < pattern.length(); i++) {
			lf[pattern.charAt(i)] = i;
		}
		
		return lf;
	}
	


    public static int searchTextBySuffixTree(String text, String pattern) {

        SuffixTree tree = new SuffixTree(text);

        return tree.search(pattern);
    }


}
